package com.atguigu.Floyd;

import java.util.Arrays;

/**
 * @author tbwtbw
 * @create 2021-11-27 19:59
 */
public class FloydAlgorithm {

    static final int N = 65535;// 表示不可以连接
    public static void main(String[] args) {
        char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        //邻接矩阵
        int[][] distance = new int[vertex.length][vertex.length];
        distance[0] = new int[] { 0, 5, 7, N, N, N, 2 };
        distance[1] = new int[] { 5, 0, N, 9, N, N, 3 };
        distance[2] = new int[] { 7, N, 0, N, 8, N, N };
        distance[3] = new int[] { N, 9, N, 0, N, 4, N };
        distance[4] = new int[] { N, N, 8, N, 0, 5, 4 };
        distance[5] = new int[] { N, N, N, 4, 5, 0, 6 };
        distance[6] = new int[] { 2, 3, N, N, 4, 6, 0 };

        int[][] path = new int[vertex.length][vertex.length];
        for (int i = 0; i < vertex.length; i++) {
            Arrays.fill(path[i], i);
        }

        Floyd(distance,path);
//        [0, 5, 7, 12, 6, 8, 2]
//        [5, 0, 12, 9, 7, 9, 3]
//        [7, 12, 0, 17, 8, 13, 9]
//        [12, 9, 17, 0, 9, 4, 10]
//        [6, 7, 8, 9, 0, 5, 4]
//        [8, 9, 13, 4, 5, 0, 6]
//        [2, 3, 9, 10, 4, 6, 0]
        // A  B  C  D  E  F  G
//      A [0, 0, 0, 5, 6, 6, 0] Path[j][k]是 k 的前驱
//      B [1, 1, 0, 1, 6, 6, 1]
//      C [2, 0, 2, 5, 2, 4, 0]
//      D [6, 3, 4, 3, 5, 3, 5]
//      E [6, 6, 4, 5, 4, 4, 4]
//      F [6, 6, 4, 5, 5, 5, 5]
//      G [6, 6, 0, 5, 6, 6, 6]

//        [0, 0, 0, 6, 6, 6, 0]这是 path[j][k]=i时的数组，好像也可以
//        [1, 1, 0, 1, 6, 6, 1]
//        [2, 0, 2, 5, 2, 4, 0]
//        [6, 3, 5, 3, 5, 3, 5]
//        [6, 6, 4, 5, 4, 4, 4]
//        [6, 6, 4, 5, 5, 5, 5]
//        [6, 6, 0, 5, 6, 6, 6]


    }

    public static void Floyd(int[][] distance,int[][] path){
        //中转点
        for (int i = 0; i < distance.length; i++) {
            //起点
            for (int j = 0; j < distance.length; j++) {
                //终点
                for (int k = 0; k < distance.length; k++) {
                    if (distance[j][k] > distance[j][i] + distance[i][k]){
                        distance[j][k] = distance[j][i] + distance[i][k];
                        path[j][k] = path[i][k];
    //pre[i][k]代表要从j走到k时，k的前一步 不能用i是因为 pre[i][k]不一定等于i 它等于从i到k的k的前一步 i到k中间可能经过了其他节点
                    }
                }
            }
        }

        for(int[] link : distance){
            System.out.println(Arrays.toString(link));
        }
        System.out.println();
        for(int[] link : path){
            System.out.println(Arrays.toString(link));
        }
    }
}
